pub fn dp_rec_mc(amount: u32) -> u32 {
  let amount = amount as usize;
  let ws: [usize; 8] = [1, 2, 5, 10, 20, 30, 50, 100];
  let mut dp = Vec::new();
  dp.resize(amount as usize + 1, usize::MAX);
  dp[0] = 0;
  for w in ws {
    for i in w..=amount {
      dp[i] = dp[i].min(dp[i - w] + 1);
    }
  }
  dp[amount] as u32
}
